package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;
import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * 3个数sum为0
 * <p>
 * TODO 排序, 之后用双指针啦. 或者二分查找啦
 *
 * @author tzp
 * @since 2020/10/18
 */
public class LC15_2 implements ArrayProblem, TwoProblem {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> result = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    r--;
                    l++;
                } else if (nums[i] + nums[l] + nums[r] > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return new ArrayList<>(result);
    }

    public static void main(String[] args) {
        System.out.println(new LC15_2().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }
}
